package com.atguigui.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 1224.最大相等频率
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/8/18 14:41
 */
public class P1224MaximumEqualFrequency {
    public static void main(String[] args) {
        Solution solution = new P1224MaximumEqualFrequency().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxEqualFreq(int[] nums) {
            //次数为 f 的数的数目
            Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
            // x出现的次数
            Map<Integer, Integer> count = new HashMap<Integer, Integer>();
            //结果            最大出现次数
            int res = 0, maxFreq = 0;
            //遍历所有数据
            for (int i = 0; i < nums.length; i++) {
                if (count.getOrDefault(nums[i], 0) > 0) {
                    //减去1
                    freq.put(count.get(nums[i]), freq.get(count.get(nums[i])) - 1);
                }
                //数据+1
                count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);

                maxFreq = Math.max(maxFreq, count.get(nums[i]));
                //个数加一
                freq.put(count.get(nums[i]), freq.getOrDefault(count.get(nums[i]), 0) + 1);
                //
                boolean ok = maxFreq == 1 ||
                        freq.get(maxFreq) * maxFreq + freq.get(maxFreq - 1) * (maxFreq - 1) == i + 1 && freq.get(maxFreq) == 1 ||
                        freq.get(maxFreq) * maxFreq + 1 == i + 1 && freq.get(1) == 1;
                //结果+1
                if (ok) {
                    res = Math.max(res, i + 1);
                }

            }

            return res;
        }
    }
}
